#include <vector>
using namespace std;
// 思路： 子集问题可以看作是每个元素有两种选择：要么包含在子集中，要么不包含在子集中。
class Solution
{
public:
    vector<vector<int>> subsets(vector<int> &nums)
    {
        vector<vector<int>> res;
        vector<int> temp;
        dfs(nums, 0, temp, res);
        return res;
    }
    void dfs(vector<int> &nums, int path_len, vector<int> &temp, vector<vector<int>> &res)
    {
        if (path_len == nums.size()) // 到达叶子节点
        {
            res.push_back(temp); // 记录当前子集
            return;
        }
        temp.push_back(nums[path_len]);     // 选择当前元素
        dfs(nums, path_len + 1, temp, res); // 继续递归
        temp.pop_back();                    // 回溯，移除最后一个元素
                                            // 不选择当前元素
        dfs(nums, path_len + 1, temp, res); // 继续递归
    }
};